package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * 134. 加油站
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/29 9:28
 */
public class CanCompleteCircuit {

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int length = gas.length;
        int[] c = new int[length];
        for (int i = 0; i < length; i++) {
            c[i] = gas[i] - cost[i];
        }
        int all = 0;
        int sum = -1;
        int item = 0;
        for (int i = 0; i < length; i++) {
            if (sum == -1) {
                if (c[i] > 0) {
                    item = i;
                    sum = c[i];
                }
            } else {
                sum += c[i];
                if (sum < 0) {
                    sum = -1;
                }
            }
            all += c[i];
        }
        if (all < 0) {
            return -1;
        }
        return item;
    }

}
